package class202205.demo25.demo21;

import java.util.Arrays;

public class TestSort {
    /**
     * 插入排序
     * 时间复杂度 O（n^2）   最好的情况是O（n）
     * 对于直接插入  最好的就是有序的   越有序  越快
     * 空间复杂度O（1）
     * 稳定性  ---> 稳定
     * 一个稳定的排序  可以实现为不稳定的排序  但是不稳定的排序  不能变成稳定的排序
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0; j--) {
                if (array[j]>tmp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;  只要J回退的时候 遇到了比tmp小的元素就结束这次比较
                    break;
                }
            }
            //j回退到了小于0的位置
            array[j+1] = tmp;
        }

    }


    public static void main(String[] args) {
        int[] array = {12,5,10,18,4,2};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}
